package com.base.dynamicprograming;

/**
 * 1014. 最佳观光组合
 *给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
 *
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
 *
 * 返回一对观光景点能取得的最高分。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-sightseeing-pair
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年12月02日 21:37
 */
public class MaxScoreSightseeingPair {

    public int maxScoreSightseeingPair(int[] values) {
        int max = values[1] + values[0] - 1, ans = max;
        //动态规划
        for (int i = 2; i < values.length; i++) {
            ans = Math.max(ans + values[i] - values[i - 1] - 1, values[i] + values[i - 1] - 1);
            max = Math.max(max, ans);
        }
        return max;
    }
}
